import common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 173. Binary Search Tree Iterator 二叉搜索树迭代器
 * https://leetcode-cn.com/problems/binary-search-tree-iterator/
 * 单调栈实现
 * 构造方法：一路到底，把根节点和它的所有左节点放到栈中；
 * 调用 next() 方法：弹出栈顶的节点；
 * 如果它有右子树，则对右子树一路到底，把它和它的所有左节点放到栈中。
 * 时间复杂度：均摊复杂度是 O(1)，调用 next() 方法的时候，如果栈顶元素有右子树，则把所有右边节点即其所有左孩子全部放到了栈中，下次调用 next() 的时候，直接访问栈顶就可以了，均摊之后时间复杂度是 O(1)。
 * 空间复杂度：O(h)，h 为数的高度，因为栈中只保留了左节点，栈中元素最多的时候，就是树的高度。
 *
 *
 */
class BSTIterator {
    private Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new LinkedList<>();
        while (root != null){
            stack.push(root);
            root = root.left;
        }
    }

    public int next() {
        TreeNode cur = stack.pop();
        TreeNode node = cur.right;
        while (node != null){
            stack.push(node);
            node = node.left;
        }
        return cur.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

class BSTIterator1 {
    private Deque<TreeNode> stack = new LinkedList<>();

    public BSTIterator1(TreeNode root) {
        TreeNode pre = null;
        while (root != null){
            if(root.left != null){
                pre = root.left;
                while(pre.right != null){
                    pre = pre.right;
                }
                pre.right = root;
                TreeNode tmp = root;
                root = tmp.left;
                tmp.left = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
    }

    public int next() {
        return stack.pollLast().val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}